1. Field of the Invention
This invention relates generally to content addressable memory searching, and more particularly to a dispatch device capable of reusing comparand data for multiple searches without requiring a host processor to reload the comparand for each search operation.
2. Description of the Related Art
In today's computer networks, data generally is divided into smaller quantities, known as packets, for transmission. Associated with each packet is a header, which includes information such as the origin of the packet and the packet's intended destination. The header is examined to classify and forward each packet through a network to its final destination, generally utilizing a content addressable memory (CAM) semiconductor device.
CAMs provide performance advantages over conventional memory devices having conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired search term, or comparand, against the entire list of entries simultaneously, giving an order-of-magnitude reduction in the search time. For example, a binary search through a non-CAM based database of 1000 entries may take ten separate search operations whereas a CAM device with 1000 entries may be searched in a single operation, resulting in significant time and processing savings. Internet routers often include a CAM for searching the address of specified data, allowing the routers to perform fast address searches to facilitate more efficient communication between computer systems over computer networks.
Conventional CAMs typically include a two-dimensional row and column content addressable memory core array of cells. In such an array, each row typically contains an address, pointer, or bit pattern entry. In this configuration, a CAM may perform “read” and “write” operations at specific addresses as is done in conventional random access memories (RAMs). However, unlike RAMs, data “search” operations that simultaneously compare a bit pattern of data against an entire list (i.e., column) of pre-stored entries (i.e., rows) can be performed.
Hence, a CAM allows the entire contents of the memory to be searched and matched instead of having to specify one or more particular memory locations in order to retrieve data from the memory. Thus, a CAM may be used to accelerate any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks.
Various algorithms are conventionally used to example the information contained in the header of a packet. For example, table-based algorithms can be implemented using CAMs. In this case, the entries of a CAM are preloaded with routing and other information, and the CAM is used as an associative array.
In operation, a CAM is presented with information, hereafter referred to as a comparand, that it compares with information previously loaded into its entries. The action of comparing a comparand with information previously loaded into the CAM entries is referred to as a look-up or search operation. If the look-up or search operation is successful, a suitable result is returned. Otherwise the CAM indicates the look-up or search operation failed or “missed.”
In a typical CAM and host processor configuration, the host processor writes header information into the Dispatch Device, which then supplies the header information to the CAM. The CAM then performs the look-up or search operation and returns the results to the dispatch device, which collects the results and provides the results to the host processor.
Data is transmitted between the host processor and the dispatch device using a bus. However, the bus width, which is the number of wires that connect the host processor to the dispatch device, is usually much less than the number of bits in the header data to be applied to the CAM as a comparand. As a result, when using a CAM that performs look-up or search operations very quickly, the time to transfer comparand information from the host processor to the dispatch device may be a significant performance bottleneck.
A header for a packet is a sequence of bits, wherein different groups of bits are utilized for different purposes. Hence, to properly classify and forward a packet, several look-up operations may be required on portions of the header. If the entire header must be re-written by the host processor into the Dispatch Device for each look-up or search operation required on a packet, the time required to classify and forward each packet can significantly affect the speed of the routing equipment.
In view of the foregoing, there is a need for systems and methods for that reduce the number of times a comparand must be written to a dispatch device. The methods should allow a comparand to be reused for multiple search operations when appropriate. In addition, when a new comparand varies from a previous comparand by very little, the method should allow the stored comparand to be slightly altered and reused to avoid requiring another comparand write to the dispatch device.